1. INTRODUCTION:

RSA system is the one of most practical public key password systems. In addition to other domain, it has successfully provided security to the electronic based commerce. Encryption of plaintext in asymmetric key encryption is based on a public key and a corresponding private key. Document authentication and digital signature are other advantages of RSA public key cryptosystem.RSA provides security to the plaintext based on factorization problem. There are PKC’s other than RSA. Those are Elgamal and Rabin’s PKC’s. These PKC’s provide security based Discrete logarithm problem.

The classical RSA cryptosystem is described in the setting of the ring Zn, the ring of integers modulo a composite integer n = pq, where p and q are two distinct odd prime integers. Many aspects of arithmetic’s over the domain of integers can be carried out to the domain of Gaussian integers Z[i], the set of all complex numbers of the form a + bi, where a and b are integers. The RSA cryptosystem was extended domain of Gaussian Integers in the papers [3] and [4]. In [3] and [4] the advantages of such extension of RSA were briefly stated in these papers.

Now in this paper, another fast variants of RSA cryptosystems is proposed using arithmetic’s modulo of Gaussian integers. Proposed scheme provides more security with same efficiency. Before doing so, in next section, we review the classical RSA PKC. Next, we introduced Gaussian integers and its properties in section 3. In section 4, we present a variant of RSA scheme based on factorization of Gaussian integers with a suitable example. Finally, we conclude with security analysis and comparison with the standard method.

2. RSA Public-Key Cryptosystem:

The classical RSA cryptosystem is described as follows: entity A generates the public-key by first generating two large random odd prime integers’ p and q, each roughly of the same size. Then, entity A computes the modulus n = p q and (n) = (p - 1) (q - 1), where is Euler’s phi function. Next, entity A selects the encryption exponent e to be any random integer in the interval (1, (n)), and which is relatively prime to (n). Using the extended Euclidean algorithm for integers, entity A finds the decryption exponent d, which is the unique inverse of e in Zn. The public-key is the pair (n, e) and A`s private key is the triplet (p, q, d).

To encrypt a message, entity B first represents the message as an integer m in Zn. Then, entity B obtains A’s public-key (n, e) and use it to compute the cipher text and sends c it to entity A. Now, to decrypt c, entity A computes and recovers the original message m.

3. Gaussian Integers:

Gaussian integer is a complex number a + bi where both a and b is integers:

Z[i] = a+bi: a,b Z . Gaussian integers, with ordinary addition and multiplication of complex numbers, form an integral domain, usually written as Z[i]. The norm of a Gaussian integer is the natural number defined .

Gaussian primes are Gaussian integer’s z = a+bi satisfying one of the following properties:

1. If both a and b are nonzero then, (a+bi) is a Gaussian prime iff is an

ordinary prime.

2. If a = 0, then bi is a Gaussian prime iff is an ordinary prime and = 3 (mod 4).

3. If b = 0, then is a Gaussian.

J.T. Cross [2] gave a full description for complete residue systems modulo prime powers of Gaussian integers.

4. RSA algorithms over the field of Gaussian Integers:

In paper [4] the RSA is extended into the field of Gaussian integers. It is presented

as follows:

Key Generation:

Generate two large Gaussian primes P and Q. Compute N = PQ.

Compute (N) = ( -1)( -1). Select a random integer e such that 1 < e < (N) and gcd (e, (N) = 1. Compute . Pair N and e is a public key, and d is the private key.

Encryption:

Given a message M (represented as a Gaussian integer) compute ciphertext

Decryption:

Compute the original message .

Now we propose the algorithms for the variant of RSA cryptosystem in Z[i] as

below:

Key Generation:

Generate b distinct large Gaussian primes and each n/b bits long.

Compute .

Compute (N) = .

Select a random integer e such that 1 < e < (N) and gcd (e, (N) = 1.

Compute .

Pair (N, e) is a public key, and is the private key.

Encryption:

Given a message M (represented as a Gaussian integer) compute cipher text

Decryption:

Compute the original message .

Following is the example in support of proposed algorithm.

Example:

Key generation

Let’s select = 19 and = 5 and = 3,

Compute the product N = = 285,

(N) = = 69120.

Choose e = 3331.

Then = mod 69120 = 29611

The public key is n = 285, e = 3331

Encryption:

Let message M = m1; m2 = (555, 444)

C = (c1; c2) =

= mod 285

= (270, 159)

Decryption:

= (270, 159) mod 285

= (555, 444)

5. Security Analyses:

The comparison of the classical RSA [11], its Gaussian Integer Domain in Z[i] [4]

and our proposed scheme is as follows:

· The generation of primes p, q in classical scheme and Gaussian primes a, b in Z[i] require the same amount of computation. Same in the case with our proposed scheme where an additional prime g in the form of 4k+3 would be generated with the same computation.

· The modified Gaussian variant provides more security than the classical method since the number of elements which are chosen to represent the message m is about square of those used in the classical case. Our proposed scheme would provide security as compare to Gaussian variant. Because, domain Z[i] in our proposed scheme provides a more extension to the range of chosen messages, which make trails more complicated as compare to the Gaussian integer domain [4].

· In [4], Euler phi function is where as in proposed scheme it is . This make the attempt to find the private key d from the public key more complicated as compare to the Gaussian variant [4] in Z[i]. Thus, our proposed scheme provides more security than the [4]. More so, the computations involved in the Gaussian variant do not require computational procedures different from those of the classical method. Same would be the case with our scheme.

· It is noted that the complexity for programs depends on the complexity of generating the public-key. Thus, the classical and proposed algorithms are equivalent since their public-key generation algorithms are identical when restricting the choice of primes to those of the form 4k+3. However, our scheme is recommended since it provides a better extension to the message space and the public exponent range as compare to classical one.

6. CONCLUSION:

We modify the computational methods in the domain of Gaussian integers. Lastly,

We show how the modified computational methods can be used to extend the RSA algorithm to the domain Z[i]. Also, we show that the modified algorithm requires a little additional computational effort than the classical one and accomplishes much greater security.

7. REFERENCES:

1. Collins, T., Hopkins, D., Langford, S., Sabin, M.: Public Key Cryptographic Apparatus and, Method. U.S.Patent #5, 848, 159, January (1997).

2. Cross, J.T. : The Eulers f -function in the Gaussian integers. Amer. Math. 55, 518–528 (1995)

3. Diffie, W., Hellman, M. : New Directions in Cryptography. IEEE Trans. on Inform. Theory, IT-22, 644–654 (1976)

4. Elkamchouchi, H., Elshenawy, K., Shaban, H.: Extended RSA cryptosystem and digital signature schemes in the domain of Gaussian integers, The 8th International Conference on Communication Systems, 1 (ICCS’02), 91–95 (2002)

5. El-Kassar, A.N., Haraty, R., Awad, Y., Debnath, N.C.: Modified RSA in the domains of Gaussian integers and polynomials over finite fields. Proc. Intl. Conf. Computer Applications in Industry and Engineering - CAINE, 298-303 (2005)

6. Gauss, C.F. :Theoria residuorum biquadraticorum. Comm. Soc. Reg. Sci. Gottingen 7, 1–34 (1832)

7. Jason Hinek, M.: Low Public Exponent Partial Key and Low private Exponent Attacks on Multi-prime rsa. Master Thesis, Waterloo, Ontario-Canada (2002)

8. Haraty, R.A., El-Kassar, A.N., Shibaro, B.: A Comparative Study of RSA Based Digital Signature Algorithms. Journal of Mathematics and Statistics 2, 354–359 (2006)

9. Menezes, A., Van Oorshot, J., Vanstone, P.C.S.A.: Handbook of Applied Cryptography. CRC Press, (1997)

10. Niven, I., Zukerman, H.S., Montegomery, H.L.: An introduction to the theory of numbers.John Wiley, New York (1991)

11. Rivest, R., Shamir, A., Adleman, L.: A Method for Obtaining Digital Signatures and Public Key Cryptosystems. Communications of the ACM 21, 120–126 (1978)

Received on 17.02.2013 Accepted on 02.03.2013

Research J. Science and Tech 5(3): July- Sept., 2013 page 300-302